
import java.util.Arrays;

public class UltimateGameBoard implements Cloneable {
    private int x = 0;
    private int y = 0;
    public int[][] grid;
    private int[][][] heuristics;
        // First dimension: Player 1 / Player 2
        // Second dimension: Streak of size 1..4
        // Third dimension: Open, left-open, right-open, closed-streaks
    private IGameLogic.Winner gameState;
    private h_node h_grid[][];

    public UltimateGameBoard(int columns, int rows, boolean no_init) {
        this.x = columns;
        this.y = rows;
        gameState = IGameLogic.Winner.NOT_FINISHED;
        grid = new int[y][x];
        heuristics = new int[3][5][4];
        h_grid = new h_node[y][x];
        if (no_init) return;
        for (int j = 0; j < y; j++)
            for (int i = 0; i < x; i++)
                grid[j][i] = 0;
        for (int i = 1; i < 3; i++)
            for (int j = 0; j < 5; j++)
                for (int k = 0; k < 4; k++)
                    heuristics[i][j][k] = 0;
        for (int j = 0; j < y; j++)
            for (int i = 0; i < x; i++)
                h_grid[j][i] = new h_node();
    }

    public UltimateGameBoard(int columns, int rows) {
        this(columns, rows, false);
    }

    private class h_node {
        public int[] dir;
        public int player;
        public boolean[][] open;
        public h_node() {
            player = 0;
            dir = new int[4];
            dir[0] = dir[1] = dir[2] = dir[3] = 0;
            open = new boolean[][] {{false, false},{false, false},{false, false},{false, false}};
        }
        public h_node Clone() {
            h_node result = new h_node();
            result.dir = this.dir.clone();
            result.player = this.player;
            for (int i=0; i < 4; i++) result.open[i] = this.open[i].clone();
            return result;
        }
        public int playerValue(int playerID, int direction) {
            if (player != playerID) return 0;
            else return dir[direction];
        }

        public void changeValue(int playerID, int direction, int value, boolean[] open) {
            this.player = playerID;
            this.dir[direction] = value;
            this.open[direction] = open;
        }
    }

    public void printHeuristic() {
        for (int player = 1; player <= 2; player++) {
            System.out.print("Player " + player + " ");
            for (int streak = 1; streak <= 4; streak++) {
                System.out.print("[" + streak + "] ");
                for (int open = 0; open < 4; open++)
                    System.out.print(heuristics[player][streak][open] + ",");
            }
            System.out.println();
        }
        for (int i = 0; i < x*3; i++) System.out.print("|"); System.out.print("  ");
        for (int i = 0; i < x*3; i++) System.out.print("-"); System.out.print("  ");
        for (int i = 0; i < x*3; i++) System.out.print("\\"); System.out.print("  ");
        for (int i = 0; i < x*3; i++) System.out.print("/"); System.out.print("  ");
        System.out.println();
        for (int j = 0; j < y; j++) {
            for (int direction = 0; direction <= 3; direction++) {
                for (int i = 0; i < x; i++) {
                    if (h_grid[j][i].open[direction][0] == true  && h_grid[j][i].open[direction][1] == true) System.out.print("@");
                    if (h_grid[j][i].open[direction][0] == true  && h_grid[j][i].open[direction][1] == false) System.out.print("<");
                    if (h_grid[j][i].open[direction][0] == false && h_grid[j][i].open[direction][1] == true) System.out.print(">");
                    if (h_grid[j][i].open[direction][0] == false && h_grid[j][i].open[direction][1] == false) System.out.print(" ");
                    System.out.print(h_grid[j][i].player + "" + h_grid[j][i].dir[direction]);
                }
                System.out.print("  ");
            }
            System.out.println();
        }
        System.out.println();
    }

    // Returns the streak counter for a field, but zero if field is outside grid bounds.
    public int h_value(int row, int column, int playerID, int direction) {
        if (row < 0 || column < 0 || row > y-1 || column > x-1 ) return 0;
        else return h_grid[row][column].playerValue(playerID, direction);
    }

    // Return true if a field is free. If it is blocked by a opponent coin or are outside the grid bounds (blocked by wall), it returns false.
    public boolean field_open(int row, int column, int playerID) {
        if (row < 0 || column < 0 || row > y-1 || column > x-1 ) return false; // Blocked by grid borders
        if (h_grid[row][column].player != 0 && h_grid[row][column].player != playerID) return false; // Block by opponent coin
        return true; // Not blocked
    }

    // Returns true if opponent has a coin in the field
    public boolean field_occupied_by_opponent(int row, int column, int playerID) {
        if (row < 0 || column < 0 || row > y-1 || column > x-1 ) return false; // Blocked by grid borders
        if (h_grid[row][column].player != 0 && h_grid[row][column].player != playerID) return true; // Block by opponent coin
        return false;
    }

    // Assign each open[0]/open[1] boolean combination an unique number for use when accessing the heuristics array
    public int open_to_int(boolean[] open) {
        if (open[0] && open [1]) return 0;
        if (open[0] && !open [1]) return 1;
        if (!open[0] && open [1]) return 2;
        if (!open[0] && !open [1]) return 3;
        System.out.println("??????????????!!");
        return -1;
    }
    final static int[][][] dir_vectors = new int[][][]
       {{{0, -1}, {0, +1}}, // vertical
        {{-1, 0}, {+1, 0}}, // horizontal
        {{-1, -1}, {+1, +1}}, // falling diagonal
        {{-1, +1}, {+1, -1}}}; // rising diagonal

    // Changes the heuristic grid and values so it corresponds to the new game state caused by the newly inserted coin.
    public void updateHeuristic(int column, int playerID) {
        int row; boolean[] open = new boolean[2];
        for (row = y - 1; row >= 0; row--) if (this.grid[row][column] == 0) break; // Find row position of newly inserted coin
        for (int direction = 0; direction <= 3; direction++) { // Do for all directions (vertical, horizontal, falling & rising diagonal)
            int[][] neighbor_directions = dir_vectors[direction]; // Get the direction vector for current direction
            int[] neighbor_values = new int[2]; // Neighbor_values store the values of the fields two neighbors relative to current direction
            for (int i = 0; i <= 1; i++)
                neighbor_values[i] = h_value(row + neighbor_directions[i][1], column + neighbor_directions[i][0], playerID, direction);
            int streak_length = neighbor_values[0] + neighbor_values[1] + 1; // Count the length of the streak caused by the newly inserted coin
            if (streak_length >= 4) // We have a winner!
                if (playerID == 1) gameState = IGameLogic.Winner.PLAYER1; else gameState = IGameLogic.Winner.PLAYER2;
            	streak_length = Math.min(4, streak_length); // If streak_length > 4, set it to 4, to prevent out of bounds error
            for (int i = 0; i <= 1; i++) // Check in both ends of streak if there is an open field or not
                open[i] = field_open(row + (neighbor_directions[i][1] * (neighbor_values[i] + 1)), column + (neighbor_directions[i][0] * (neighbor_values[i] + 1)), playerID);
            heuristics[playerID][streak_length][open_to_int(open)] += 1;
            h_grid[row][column].changeValue(playerID, direction, streak_length, open.clone()); // Update field where coin were just inserted
            for (int i = 0; i <= 1; i++) {// Check if the newly inserted coin blocks some opponent streak, and and change the opponent streaks open variables accordingly
                if (field_occupied_by_opponent(row + neighbor_directions[i][1], column + neighbor_directions[i][0], playerID)) {
                    int opponent_val        = h_grid[row + neighbor_directions[i][1]][column + neighbor_directions[i][0]].dir[direction];
                    boolean[] opponent_open = h_grid[row + neighbor_directions[i][1]][column + neighbor_directions[i][0]].open[direction].clone();
                    heuristics[3 - playerID][opponent_val][open_to_int(opponent_open)] -= 1;
                    opponent_open[1-i] = false;
                    heuristics[3 - playerID][opponent_val][open_to_int(opponent_open)] += 1;
                    for (int j = 1; j <= opponent_val; j++) {
                        h_grid[row + neighbor_directions[i][1] * j][column + neighbor_directions[i][0] * j].open[direction][1-i] = false;
                    }
                }
            }
            for (int i = 0; i <= 1; i++) { // Propagate the new streak value to the two old "subparts" of streak.
                if (neighbor_values[i] == 0) continue;
                boolean[] neighbor_open = h_grid[row + neighbor_directions[i][1]][column + neighbor_directions[i][0]].open[direction].clone();
                heuristics[playerID][neighbor_values[i]][open_to_int(neighbor_open)] -= 1;
                for (int j = 1; j <= neighbor_values[i]; j++)
                    h_grid[row + neighbor_directions[i][1] * j][column + neighbor_directions[i][0] * j].changeValue(playerID, direction, streak_length, open.clone());
            }
        }
    }

    public int columns() {
        return x;
    }

    public int rows() {
        return y;
    }

    // Returns count of different actions possible (= number of non-full columns)
    public int actionsCount() {
        int openColumns = 0;
        for (int i = 0; i < x; i++)
            if (grid[0][i] == 0)
                openColumns++;
        return openColumns;
    }

    // Returns a list of possible actions (that is, columns where a coin can be inserted, i.e. not full)
    public int[] actions() {
        int[] possibleActions = new int[actionsCount()];
        int position = 0;
        for (int i = 0; i < x; i++)
            if (grid[0][i] == 0)
                possibleActions[position++] = i;
        return possibleActions;
    }

    @Override
    public UltimateGameBoard clone() {
        UltimateGameBoard result = new UltimateGameBoard(this.x, this.y, true); // New GameBoard with no init, since this method clones values.
        for (int i = 0; i < y; i++)
            result.grid[i] = this.grid[i].clone(); // Java can only clone a one-dimensional array, so this is needed
        for (int player = 0; player < 3; player++)
            for (int streak = 0; streak < 5; streak++)
                result.heuristics[player][streak] = this.heuristics[player][streak].clone();
        result.gameState = this.gameState;
        for (int j = 0; j < y; j++)
            for (int i = 0; i < x; i++)
                result.h_grid[j][i] = this.h_grid[j][i].Clone();
        return result;
    }
        
    // Returns a new GameBoard with playerID coin inserted in given column
    public UltimateGameBoard result(int column, int playerID) {
        UltimateGameBoard result = this.clone();
        result.insertCoin(column, playerID);
        return result;
    }

    // Returns a list of GameBoards, each corresponding to the result of a possible move
    public UltimateGameBoard[] results(int playerID) {
        UltimateGameBoard[] results = new UltimateGameBoard[actionsCount()];
        int position = 0;
        for (int i = 0; i < x; i++)
            if (grid[0][i] == 0)
                results[position++] = result(i, playerID);
        return results;
    }

    // Returns a list of GameBoards, each corresponding to the result of a possible move,
    // and sorted according to heuristic value, best first
    public UltimateGameBoard[] sortedResults(int playerID) {
        UltimateGameBoard[] results = results(playerID);
        final int p = playerID, o = 3 - playerID;
        Arrays.sort(results, new java.util.Comparator<UltimateGameBoard>() {
            public int compare(UltimateGameBoard board1, UltimateGameBoard board2) {
                return (board2.heuristic(p)-board2.heuristic(o)) - (board1.heuristic(p)-board1.heuristic(o)); // b - a
            }
        });
        return results;
    }

    // Inserts a coin belonging to playerID in given column
    public void insertCoin(int column, int playerID) {
        updateHeuristic(column, playerID);
        for (int i = y - 1; i >= 0; i--)
            if (this.grid[i][column] == 0) {
                this.grid[i][column] = playerID;
                if (actionsCount() == 0 && gameState == IGameLogic.Winner.NOT_FINISHED) gameState = IGameLogic.Winner.TIE; // Works, but costs a little, since actionsCount() does iteration
                return;
            }
    }

    // method to print out the local board for test purposes
    public void print() {
        for (int j = 0; j < y; j++) {
            for (int i = 0; i < x; i++)
                System.out.print(":" + grid[j][i]);
            System.out.println();
        }
        System.out.println();
    }
    
    final int[][] streak_weights = new int[][]
        {{0,0,0,0},                  // 0 - streak
        {200,100,100,0},             // 1 - streak
        {1000,500,500,0},            // 2 - streak
        {5000,3000,3000,0},          // 3 - streak
        {50000, 50000, 50000, 50000} // 4 - streak
    };

    public int heuristic(int playerID) {
    	// return 999999 if there is a winner
    	for (int open = 0; open < 4; open++) {
			if (heuristics[playerID][4][open] > 0) return 999999;
		}
    	// calculate board value otherwise
        int h = 0;
        for (int streak = 1; streak <= 4; streak++)
            for (int open = 0; open < 4; open++) {
                h += heuristics[playerID][streak][open] * streak_weights[streak][open];
            }
        return h;
    }
    
    public IGameLogic.Winner gameState() {
        return gameState;
    }
}